package P1_2;

import java.util.Scanner;
//约瑟夫环问题
public class 约瑟夫环 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入人数:");
        int N=sc.nextInt();
        System.out.println("请输入报到几被杀:");
        int M=sc.nextInt();
        Game g=new Game();
        for(int i=0;i<N;i++){
            g.add(new GPerson(i));
        }
        g.play(M);
        System.out.println("剩下的是"+g.last()+"号");
    }
}
class Game{
    private GPerson cur,head=null;
    private int count=0;

    public void add(GPerson p) {
        if(head==null){
        head=p;
            p.setPrev(p);
            p.setNext(p);
        }
        else{
            GPerson last=head.getPrev();
            last.setNext(p);
            p.setNext(head);
            head.setPrev(p);
            p.setPrev(last);
        }
        count++;
    }

    public void play(int M) {
        int num=1;
        cur=head;
        while(count>1){
            cur.talkNum(num);
            if(num==M){
                GPerson c=cur;
                cur=cur.getNext();
                kill(c);
                count--;
            }
            else{
                cur=cur.getNext();
            }
            num=num%M+1;
        }
    }

    private void kill(GPerson c) {
        GPerson prev=c.getPrev();
        GPerson next=c.getNext();
        prev.setNext(next);
        next.setPrev(prev);
        System.out.println("杀掉"+c.getId());
    }

    public int last() {
        return cur.getId();
    }
}
class GPerson{
    private int id;
    private GPerson prev,next;

    public int getId() {
        return id;
    }
    public GPerson(int id) {
        this.id=id;
    }
    public GPerson getPrev() {
        return prev;
    }

    public void setPrev(GPerson prev) {
        this.prev = prev;
    }

    public GPerson getNext() {
        return next;
    }
    public void setNext(GPerson next) {
        this.next = next;
    }

    public void talkNum(int num) {
        System.out.println(id+"报数"+num);
    }
}